package leetcode_2501_2600;

public class LeeCode_2565 {
    public static void main(String[] args) {
        System.out.println(minimumScore("abacaba", "bzaa"));
        System.out.println(minimumScore("cde", "xyz"));
    }
    private static int minimumScore(String s, String t) {
        char[] cs = s.toCharArray(), ts = t.toCharArray();
        int n = s.length(), m = t.length();
        int[] suf = new int[n + 1];
        suf[n] = m;
        for(int i = n - 1, j = m - 1; i >= 0; --i){
            if (j >= 0 && cs[i] == ts[j]){
                --j;
            }
            suf[i] = j + 1;
        }
        int ans = suf[0];
        if (ans == 0)
            return ans;
        for (int i = 0, j = 0; i < n; ++i) {
            if (cs[i] == ts[j]){
                ans = Math.min(ans, suf[i + 1] - ++j);
            }
        }
        return ans;
    }
}
